﻿#pragma once
#include "stdafx.h"
/*
第29题：两数相除
给定两个整数，被除数 dividend 和除数 divisor。将两数相除，要求不使用乘法、除法和 mod 运算符。

返回被除数 dividend 除以除数 divisor 得到的商。

整数除法的结果应当截去（truncate）其小数部分，例如：truncate(8.345) = 8 以及 truncate(-2.7335) = -2

 

 示例 1:

 输入: dividend = 10, divisor = 3
 输出: 3
 解释: 10/3 = truncate(3.33333..) = truncate(3) = 3
 示例 2:

 输入: dividend = 7, divisor = -3
 输出: -2
 解释: 7/-3 = truncate(-2.33333..) = -2

 来源：力扣（LeetCode）
 链接：https://leetcode-cn.com/problems/divide-two-integers
 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

 解题思路，当限制了乘法，除法，还有 取余mod，我们会考虑到位移，位移就相当于乘除法，只不过是以2的倍数，
 这就需要一点数学功底了，不过从小学学习就知道乘法的基本就是加法，而除法的本质是乘法。这样我们使用加法，
 减法就可以实现乘除法的功能。本题目要么考察位运算，要么考察乘法的基本写法。

*/

int divide(int dividend, int divisor) 
{
	int sign;
	if ((dividend >= 0 && divisor > 0) || (dividend <= 0 && divisor < 0)) {
		sign = 0;
	}
	else {
		sign = 1;
	}
	long a = abs(dividend), cmp = abs(divisor);
	long res = 0, partial_sum = 1;
	int abs_divisor = cmp;
	if (a < cmp) return 0;
	while ((cmp << 1) < a) {
		cmp = cmp << 1;
		partial_sum = partial_sum << 1;
	}
	while (a >= abs_divisor) {
		a -= cmp;
		res += partial_sum;
		while (cmp > a) {
			cmp = cmp >> 1;
			partial_sum = partial_sum >> 1;
		}
	}
	if (sign == 1) {
		if (-res < INT_MIN) return INT_MAX;
		else return -res;
	}
	else {
		if (res > INT_MAX) return INT_MAX;
		else return res;
	}


}


void divideDemo()
{
	int a = 0;
	a = divide(9,3);
	cout << a << endl;

}
